#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <utility>
using namespace std;

#define mm(a, n) memset(a, n, sizeof a)
#define mk(a, b) make_pair(a, b)

const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<LL, LL> PLL;
typedef pair<int, LL> PIL;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}


const int N = 1e6 + 10;

LL a, b, c, d, n;

vector<int> vec[60];

// 计算 n 每一位的和
int calc_sum(int n) {
    int res = 0;
    while (n) res += n % 10, n /= 10;
    return res;
}

// 计算函数值
LL calc(LL x, LL a, LL b) {
    return a * x * x + b * x;
}

inline void solution() {
    int T;
    scanf("%d", &T);
    // 预处理数据
    for (int i = 1; i < N; i ++ ) 
        vec[calc_sum(i)].push_back(i);
    
    while (T -- ) {
        LL res = INF_LL;
        scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &d, &n);
        for (int i = 1; i <= 54; i ++ ) {
            // f(x) = (a * g(x) + b) * x^2 + (c * g(x)^2 + d * g(x)) * x;
            LL A = a * i + b;
            LL B = c * i * i + d * i;
            
            if (vec[i].size() == 0) continue;
            int l = 0, r = upper_bound(vec[i].begin(), vec[i].end(), n) - vec[i].begin() - 1;
            if (r < 0) continue;
            if (A > 0) {
                LL ansL = INF_LL, ansR = INF_LL;
                while (l <= r)
                {
                    int lmid = l + (r - l) / 3;
                    int rmid = r - (r - l) / 3;
                    ansL = calc(vec[i][lmid],A,B),ansR = calc(vec[i][rmid],A,B);
                    if(ansL <= ansR)
                        r = rmid - 1;
                    else
                        l = lmid + 1;
                }
                res = min(res, min(ansL, ansR));
                
            } else {
                res = min(res, calc(1ll * vec[i][0], A, B));
                res = min(res, calc(1ll * vec[i][r], A, B));
            }
        }
        printf("%lld\n", res);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    quickread();
    solution();
    return 0;
}